package MiddlePractice;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Demo752 {
//	752. 打开转盘锁
//	你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
//	每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
//
//	锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
//
//	列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
//
//	字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
	
	public int openLock(String[] deadends, String target) {
		Queue<String> queue = new LinkedList<>();
		Set<String> memo = new HashSet<>();
		
		int step = 0;
		queue.offer("0000");
		memo.add("0000");
		
		while(!queue.isEmpty()) {
			
			int qSize = queue.size();
			
			for(int k=0; k<qSize; k++) {
				
				String choice = queue.poll();
				
				//检查是否在非法列表里
				if(contain(deadends, choice)) {
					continue;
				}
				
				if(target.equals(choice)) {
					return step;
				}
				
				for(int i=0; i<4; i++) {
					//i位有两种操作：up或者down  每次要判断一下是否已被访问过
					String up = turnUp(choice, i);
					String down = turnDown(choice, i);
					
					if(!memo.contains(up)) {
						queue.offer(up);
						memo.add(up);
					}
					if(!memo.contains(down)) {
						queue.offer(down);
						memo.add(down);
					}
				}
			}
			
			step++;
		}
		return -1;
    }
	
	private boolean contain(String[] deadends, String choice) {
		
		for(String str : deadends) {
			if(choice.equals(str)) {
				return true;
			}
		}
		
		return false;
	}

	private String turnUp(String choice, int index) {
		char[] charArr = choice.toCharArray();
		
		if(charArr[index] == '9') {
			charArr[index] = '0';
		}
		else {
			charArr[index] += 1;
		}
		
		return new String(charArr);
	}
	
	private String turnDown(String choice, int index) {
		char[] charArr = choice.toCharArray();
		
		if(charArr[index] == '0') {
			charArr[index] = '9';
		}
		else {
			charArr[index] -= 1;
		}
		
		return new String(charArr);
	}

}
